package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/6/12 20:26
 * 重排链表
 * 给定的单链表: 0 -> 1 -> 2 -> 3
 * 重新排序为: 0 -> 3 -> 1 -> 2
 * 算法：链表
 * 先找到链表的中点
 * 将中点后的链表反转
 */
public class NC2 {

    public void reorderList(ListNode head) {
        if (head == null) return;
        // 1. 使用快慢指针获取链表的中间节点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. 将中间节点的后面链表翻转
        // 这里要将 slow 与后面的链表切断, 不然会形成环, 从而导致死循环
        ListNode tmp = slow.next;
        slow.next = null;
        slow = reverse(tmp);
        // 3. 将 fast 指向 head, 开始重排
        fast = head;
        while (slow != null && fast != null) {
            ListNode ne1 = slow.next, ne2 = fast.next;
            fast.next = slow;
            slow.next = ne2;
            fast = ne2;
            slow = ne1;
        }
    }
    ListNode reverse(ListNode node) {
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

}
